package com.leetcode.algorithm.y22.m07.w5;

import java.util.PriorityQueue;

import com.leetcode.algorithm.common.ListNode;

/**
 * 23. 合并K个升序链表
 * 
 * https://leetcode.cn/problems/merge-k-sorted-lists/
 * 
 * @author jie.deng
 *
 */
class Question0023Solution01 {

	public ListNode mergeKLists(ListNode[] lists) {
		PriorityQueue<ListNode> queue = new PriorityQueue<>((t1, t2) -> t1.val - t2.val);
		for (ListNode listNode : lists) {
			if (listNode != null) {
				queue.add(listNode);
			}
		}

		ListNode sentinel = new ListNode();
		ListNode cur = sentinel;
		while (!queue.isEmpty()) {
			ListNode tmp = queue.poll();
			cur.next = tmp;
			cur = cur.next;
			if (tmp.next != null) {
				queue.offer(tmp.next);
			}
		}
		return sentinel.next;
	}

}